#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "list"
#include "unordered_map"

#include ""
using namespace std;
/*HJJ QQ479287006
 *请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

 

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */


int size;
list<pair<int,int>> listp;
//这个传入的是迭代器类型 通常是类型后::iterator
unordered_map<int, list<pair<int,int>>::iterator > mp;
LRUCache(int capacity) {
    size=capacity;
}

int get(int key) {

    auto result= mp.find(key);
    if (result!=mp.end())
    {
        //这里移动元素比较好 获取list 元素位置

        listp.splice(listp.begin(),listp,result->second);

        return  result->second->second;
    }

    return -1;
}

void put(int key, int value) {

    auto result= mp.find(key);
    if (result!=mp.end())
    {
        //这里移动元素比较好 获取list 元素位置
        listp.splice(listp.begin(),listp,result->second);
        listp.begin()->second=value;
        mp[key]=listp.begin();
        return ;
    }

    listp.emplace_front(key,value);
    mp.insert(make_pair(key,listp.begin()));

    if (listp.size()> size)
    {
        auto re= listp.back();
        listp.pop_back();
        //同时需要删除map
        mp.erase(re.first);
    }

}

//    l1.splice(l1.end(),l1,l1.begin()); 对l1 进行操作把 l1的开始 粘到结尾那边

//void put1(int key, int value) {
//
//
//
//    listp.emplace_back(key,value);
//    //注意end() 并不是最后一个元素 而是指向null
//    //想要获取迭代器前一个使用  auto last = std::prev(listp.end()); 还有一个next 迭代器  ++ -- 也可以
//
//
//    mp.insert(make_pair(key,listp.end()-1));
//
//    if (listp.size()> size)
//    {
//        auto re= listp.front();
//        listp.pop_front();
//        //同时需要删除map
//        mp.erase(re.first);
//    }
//
//}